1. Technical Field
The present invention relates to language translation systems and more particularly to a phrase-based translation system built within a finite state transducer (FST) framework that achieves high memory efficiency, high speed and high translation accuracy.
2. Description of the Related Art
The need for portable machine translation devices has never been more apparent; however, existing methods for statistical machine translation generally require more resources than are readily available in small devices.
One of the applications for machine translation is a handheld device that can perform interactive machine translation. However, the great majority of research in machine translation has focused on methods that require at least an order of magnitude more resources than are readily available on e.g., personal digital assistants (PDAs).
The central issue in limited-resource statistical machine translation (SMT) is translation speed. Not only are PDA's much slower than PC's, but interactive applications require translation speeds at last as fast as real time. In practice, it may be difficult to begin translation until after a complete utterance has been entered (e.g., because speech recognition is using all available computation on the PDA). In this case, translation speeds of much faster than real time are needed to achieve reasonable latencies.
Various translation methods have been implemented in the prior art using weighted finite-state transducers (WFSTs). For example, Knight et al in “Translation with Finite-State Devices”, 4th AMTA Conference 1998, describe a system based on word-to-word statistical translation models, Bangalore et al. in “A Finite-State Approach to Machine Translation”, NAACL 2001, use WFST's to select and reorder lexical items for the translation. More recently, in, the present inventors in Zhou et al. “Constrained Phrase-Based Translation Using Weighted Finite-State Transducers”, Proc. ICASSP '05, 2005, describe a constraint-phrase based translation system using WFST's, where a limited number of frequent word sequences and syntactic phrases are re-tokenized in the training data. Kumar et al. in “A Weighted Finite State Transducer Translation Template Model for Statistical Machine Translation”, Journal of Natural Language Engineering 11(3), 2005, implement a phrase-based approach of the alignment template translation models using WFSTs.
In the prior art, a desirable way to handle translation using the WFST scheme is to first build a search hypothesis transducer by composing component translation models, and secondly, the input sentence to be translated is represented as a FSA (finite state acceptor), which is composed with the transducer as a common practice. Finally, the translation is the best path in the composed machine.
However, a phrase-based translation implemented in the previous studies is not able to be composed into a static lattice offline due to practical memory constraints. In order to make the chain composition computationally tractable, some of the key component transducers have to be collapsed into smaller machines through online composing with the given input. For example, in Kumar et al., the integrated transducers have to be built specifically for a given input, achieved by a sequence of composition operations on the fly.
A significant disadvantage of such previous studies is the heavy online computational burden, and the loss of advantages of the FST approach that optimal algorithms can be applied offline for improved performance. As a result, the computational speeds of these schemes are significantly slower than those of phrase-based systems not using FST's. Previous FST systems translate at a speed around 10 words or less per second compared to the typical speeds that lie between 100 and 1600 words per second for full blown computers.